翻訳と辞書 Words near each other ・ Circuit Merit ・ Circuit minimization for Boolean functions ・ Circuit Mont-Tremblant ・ Circuit no Ōkami ・ Circuit noise level ・ Circuit of culture ・ Circuit of Ireland Rally ・ Circuit of the Americas ・ Circuit of Wales ・ Circuit Park Zandvoort ・ Circuit party ・ Circuit Paul Armagnac ・ Circuit Planete ・ Circuit preacher ・ Circuit quantum electrodynamics ・ Circuit rank ・ Circuit reliability ・ Circuit restoration ・ Circuit Ricardo Tormo ・ Circuit rider ・ Circuit rider (religious) ・ Circuit rider (technology) ・ Circuit rider (water/wastewater) ・ Circuit Riverside Speedway Ste-Croix ・ Circuit satisfiability problem ・ Circuit Scribe ・ Circuit Showdown ・ Circuit split ・ Circuit Switched Data ・ Circuit switching Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Circuit rank ： ウィキペディア英語版 Circuit rank In graph-theoretic mathematics, the circuit rank of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. Alternatively, it can be interpreted as the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank is easily computed using the formula :$r\; =\; m\; -\; n\; +\; c$, where is the number of edges in the given graph, is the number of vertices, and is the number of connected components. 〔.〕 It is also possible to construct a minimum-size set of edges that breaks all cycles efficiently, either using a greedy algorithm or by complementing a spanning forest. The circuit rank is also known as the cyclomatic number or nullity of the graph. It can be explained in terms of algebraic graph theory as the dimension of the cycle space of a graph, in terms of matroid theory using the corank of a graphic matroid, and in terms of topology as one of the Betti numbers of a topological space derived from the graph. It counts the ears in an ear decomposition of the graph, forms the basis of parameterized complexity on almost-trees, and has been applied in software metrics as part of the definition of cyclomatic complexity of a piece of code. Under the name of cyclomatic number, the concept was introduced by Gustav Kirchhoff. ==Matroid rank and construction of a minimum feedback edge set== The circuit rank of a graph may be described using matroid theory as the corank of the graphic matroid of .〔.〕 Using the greedy property of matroids, this means that one can find a minimum set of edges that breaks all cycles using a greedy algorithm that at each step chooses an edge that belongs to at least one cycle of the remaining graph. Alternatively, a minimum set of edges that breaks all cycles can be found by constructing a spanning forest of and choosing the complementary set of edges that do not belong to the spanning forest. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Circuit rank」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.